using System;
using System.Collections.Generic;
using System.Linq;

namespace Sail.Utility
{
    public static class DependencyOrdering
    {
        private class Linkage<T>
        {
            public T Element { get; set; }
            public bool Used { get; set; }
        }

        public static IEnumerable<T> OrderByDependenciesAndPriorities<T>(this IEnumerable<T> elements,
                                                                         Func<T, T, bool> hasDependency,
                                                                         Func<T, int> getPriority)
        {
            var population = elements.Select(d => new Linkage<T>
                                                      {
                                                          Element = d
                                                      }).OrderBy(item => getPriority(item.Element)).ToArray();

            var result = new List<T>();
            foreach (var item in population)
            {
                Add(item, result, population, hasDependency, getPriority);
            }

            for (int i = 1; i < result.Count; i++)
            {
                int bestPosition = BestPriorityPosition(result, i, hasDependency, getPriority);
                SwitchAndShift(result, i, bestPosition);
            }

            return result;
        }

        private static void Add<T>(Linkage<T> item, ICollection<T> list, IEnumerable<Linkage<T>> population,
                                   Func<T, T, bool> hasDependency, Func<T, int> getPriority)
        {
            if (item.Used)
                return;

            item.Used = true;

            foreach (var dependency in population.Where(dep => hasDependency(item.Element, dep.Element)))
            {
                Add(dependency, list, population, hasDependency, getPriority);
            }

            list.Add(item.Element);
        }

        private static int BestPriorityPosition<T>(List<T> list, int index, Func<T, T, bool> hasDependency,
                                                   Func<T, int> getPriority)
        {
            int bestPriority = getPriority(list[index]);
            int bestIndex = index;

            for (int i = index - 1; i >= 0; i--)
            {
                if (hasDependency(list[index], list[i]))
                {
                    return bestIndex;
                }

                int currentPriority = getPriority(list[i]);
                if (currentPriority > bestPriority)
                {
                    bestIndex = i;
                }
            }

            return bestIndex;
        }

        private static bool SwitchAndShift<T>(List<T> list, int initialPosition, int finalPosition)
        {
            if (initialPosition < finalPosition)
            {
                throw new ArgumentException("finalPosition");
            }

            if (initialPosition != finalPosition)
            {
                T temp = list[initialPosition];

                for (; initialPosition > finalPosition; initialPosition--)
                {
                    list[initialPosition] = list[initialPosition - 1];
                }

                list[finalPosition] = temp;

                return true;
            }

            return false;
        }
    }
}